#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    // bool isSymmetric(TreeNode *root)
    // {
    //     queue<TreeNode *> que;
    //     if (root != nullptr)
    //     {
    //         que.push(root);
    //     }
    //     while (!que.empty())
    //     {
    //         int length = que.size();
    //         vector<int> vec;
    //         for (int i = 0; i < length; i++)
    //         {
    //             TreeNode *node = que.front();
    //             que.pop();
    //             if (node->left)
    //             {
    //                 que.push(node->left);
    //                 vec.push_back(node->left->val);
    //             }
    //             else
    //             {
    //                 vec.push_back(200);
    //             }
    //             if (node->right)
    //             {
    //                 que.push(node->right);
    //                 vec.push_back(node->right->val);
    //             }
    //             else
    //             {
    //                 vec.push_back(200);
    //             }
    //         }
    //         int vec_size = vec.size();
    //         for (int i = 0, j = vec_size - 1; i < j; i++, j--)
    //         {
    //             if (vec[i] != vec[j])
    //             {
    //                 return false;
    //             }
    //         }
    //     }
    //     return true;
    // }

    // bool recursion(TreeNode *left, TreeNode *right)
    // {
    //     if (left == nullptr && right != nullptr)
    //     {
    //         return false;
    //     }
    //     else if (left != nullptr && right == nullptr)
    //     {
    //         return false;
    //     }
    //     else if (left == nullptr && right == nullptr)
    //     {
    //         return true;
    //     }
    //     else if (left->val != right->val)
    //     {
    //         return false;
    //     }
    //     bool flag1 = recursion(left->left, right->right);
    //     bool flag2 = recursion(left->right, right->left);
    //     return flag1 && flag2;
    // }

    // bool isSymmetric(TreeNode *root)
    // {
    //     if (root == nullptr)
    //     {
    //         return true;
    //     }
    //     return recursion(root->left, root->right);
    // }

    bool isSymmetric(TreeNode *root)
    {
        if (root == nullptr)
        {
            return true;
        }
        queue<TreeNode *> que;
        que.push(root->left);
        que.push(root->right);
        while (!que.empty())
        {
            TreeNode *left = que.front();
            que.pop();
            TreeNode *right = que.front();
            que.pop();
            if (left == nullptr && right == nullptr)
            {
                continue;
            }
            if (left == nullptr || right == nullptr || left->val != right->val)
            {
                return false;
            }
            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }
};

int main()
{
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(3);
    Solution sol;
    cout << sol.isSymmetric(root) << endl;
    return 0;
}